import java.util.HashSet;
import java.util.Set;

/**
 * @author yexiebao
 * @date 2025/5/17
 */
public class DetectCycle {
    // 哈希表
   public static ListNode detectCycle(ListNode head) {
       if(head == null || head.next == null){
           return null;
       }
       Set<ListNode> visited = new HashSet<>();
       ListNode curr  = head;
       while(curr.next != null){
           if(visited.contains(curr)){
               return curr;
           }else{
               visited.add(curr);
           }
           curr = curr.next;
       }
       return null;
   }
   //快慢指针
    public static ListNode detectCycleUseDoublePoint(ListNode head) {
        if(head == null || head.next == null){
            return null;
        }
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                ListNode ptr  = head;
                while(ptr != slow){
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}